package com.lzq.leetcode.hoot100;

import java.util.HashMap;
import java.util.Map;

public class s146 {

    private int capacity;
    private int size;
    private Map<Integer, Node> map;
    private Node head;

    public s146(int capacity) {
        this.capacity = capacity;
        size = size;
        map = new HashMap<>();
        head = new Node();
        head.next = head;
        head.pre = head;
    }

    public int get(int key) {

        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {

        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.val = value;
            remove(node);
        } else {
            node = new Node(key, value);
            map.put(key, node);
            ++size;
        }
        addToHead(node);
        if (size > capacity) {
            // 找到最后一个
            node = head.pre;
            remove(node);
            map.remove(node.key);
            --size;
        }
    }

    private void remove(Node node) {
        node.pre.next = node.next;
        if (node.next != null)  node.next.pre = node.pre;
    }

    private void addToHead(Node node) {

        if (head.next != null)  head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }

    class Node {
        Node pre;
        Node next;
        int key;
        int val;

        Node(){}
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        s146 s146 = new s146(2);
        s146.put(1, 1);
        s146.put(2, 2);
        System.out.println(s146.get(1));
        s146.put(3, 3);
        System.out.println(s146.get(2));
        s146.put(4, 4);
        System.out.println(s146.get(1));

        System.out.println(s146.get(3));
        System.out.println(s146.get(4));
    }
}
